package study.datastructure.tree;

/**
 * 二叉搜索树
 */
public class BinarySearchTree {

    // 二叉搜索树的根节点
    private Node root;

    /**
     * 内部类定义节点结构
     */
    private static class Node {
        int key;  // 节点存储的键
        int val;  // 节点存储的值
        Node left;  // 左子节点
        Node right;  // 右子节点

        Node(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }

    /**
     * 插入节点的方法（目前只是架子，具体逻辑待完善
     */
    public void insert(int value) {
        root = insertRec(root, value);
    }

    /**
     * @param current
     * @param value
     * @return
     */
    private Node insertRec(Node current, int value) {
        if (current == null) {
            return new Node(value);
        }

        if (value < current.val) {
            // 待完善向左子树插入的逻辑
            current.left = insertRec(current.left, value);
        } else if (value > current.val) {
            // 待完善向右子树插入的逻辑
            current.right = insertRec(current.right, value);
        }

        return current;
    }


    // 查找节点的方法（架子，具体逻辑可后续添加）
    public boolean search(int value) {
        return doSearchRec(root, value);
    }

    private boolean doSearchRec(Node current, int value) {
        if (current == null) {
            return false;
        }

        if (value == current.val) {
            return true;
        } else if (value < current.val) {
            return doSearchRec(current.left, value);
        } else {
            return doSearchRec(current.right, value);
        }
    }

    /**
     * 迭代法
     *
     * @param key
     * @return
     */
    public Object get1(int key) {
        Node root = this.root;
        while (root != null) {
            if (key > root.key) {
                root = root.left;
            } else if (key < root.key) {
                root = root.right;
            } else {
                return root.val;
            }
        }
        return null;
    }

    public Object get(int key) {
        return doGetRec(root, key);
    }

    private Object doGetRec(Node node, int key) {
        if (node == null) {
            return null;
        }

        if (key > node.key) {
            return doGetRec(node.left,key);
        } else if (key < node.val) {
            return doGetRec(node.right,key);
        } else {
            return node.val;
        }
    }

    // 删除节点的方法（架子，具体复杂逻辑需后续添加）
    public void delete(int value) {
        root = deleteRec(root, value);
    }

    private Node deleteRec(Node current, int value) {
        if (current == null) {
            return current;
        }

        if (value < current.val) {
            current.left = deleteRec(current.left, value);
        } else if (value > current.val) {
            current.right = deleteRec(current.right, value);
        } else {
            // 处理有一个子节点或者两个子节点等不同情况的删除逻辑待完善
            if (current.left == null) {
                return current.right;
            } else if (current.right == null) {
                return current.left;
            }
            // 更多复杂情况待补充
        }

        return current;
    }

}